package Test;

public class Test02 {
    public boolean canPartition(int[] nums)
 {
         int n = nums.length, sum = 0;
         for(int x : nums) sum += x;
         if(sum % 2 == 1) return false; // 如果不能平分，直接返回 false

         int aim = sum / 2;
         boolean[][] dp = new boolean[n + 1][aim + 1]; // 建表
         for(int i = 0; i <= n; i++) dp[i][0] = true; // 初始化
         for(int i = 1; i <= n; i++) // 填表
             for(int j = 1; j <= aim; j++)
         {
             dp[i][j] = dp[i - 1][j];
             if(j >= nums[i - 1])
                 dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
             }
         return dp[n][aim];
         }
    public int minimumDeleteSum(String s1, String s2)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if(s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + s1.charAt(i-1));
            }
        int sum = 0; // 统计元素和
         for(char ch : s1.toCharArray()) sum += ch;
         for(char ch : s2.toCharArray()) sum += ch;
         return sum - dp[m][n] - dp[m][n];
         }
    public boolean isInterleave(String s1, String s2, String s3)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = s1.length(), n = s2.length();
        if(m + n != s3.length()) return false; // 处理下边界条件
        s1 = " " + s1; s2 = " " + s2; s3 = " " + s3;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true; // 初始化
        for(int j = 1; j <= n; j++) // 初始化第⼀⾏
            if(s2.charAt(j) == s3.charAt(j)) dp[0][j] = true;
            else break;
        for(int i = 1; i <= m; i++) // 初始化第⼀列
            if(s1.charAt(i) == s3.charAt(i)) dp[i][0] = true;
            else break;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j])
                        || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
        return dp[m][n];
    }
    public boolean isMatch2(String ss, String pp)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = ss.length(), n = pp.length();
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2)
            if(p[j] == '*') dp[0][j] = true;
            else break;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(p[j] == '*')
                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] ==
                            s[i]) && dp[i - 1][j];
                else
                    dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i - 1][j -
                            1];

         return dp[m][n];
         }
    public boolean isMatch(String ss, String pp)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int m = ss.length(), n = pp.length();
        ss = " " + ss; pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 1; j <= n; j++)
            if(p[j] == '*') dp[0][j] = true;
            else break;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(p[j] == '*')
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else
                    dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i - 1][j - 1];
        return dp[m][n];
    }
    public int maxUncrossedLines(int[] nums1, int[] nums2)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        return dp[m][n];
    }
    public int numDistinct(String s, String t)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = t.length(), n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0; j <= n; j++) dp[0][j] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i][j - 1];
                if(t.charAt(i - 1) == s.charAt(j - 1))
                    dp[i][j] += dp[i - 1][j - 1];
            }
        return dp[m][n];
    }
}
